The present invention relates to data security, encryption, and, generating and using electronic signatures to verify the identity of a communicating party.
Most public key cryptosystems involve either a factoring problem or a discrete logarithm (DL) problem. The factoring problem is, given a not-prime number, find its complete factorization into prime numbers. The DL problem is, given a group G generated by g and an element h in G, find an integer m such that gm=h, that is, evaluate logg h. Several proposed schemes for public key cryptosystems rely on the computational difficulty of finding a DL in a multiplicative group of a finite field.
Public key cryptosystems encompass public key encryption schemes and digital signature schemes. Assume each user has a public key and a private key, which is not necessarily true for all schemes, and that party A wishes to send a secure message to party B. In a public key encryption scheme, party A uses party B""s public key to encrypt, and then party B uses its own public and private keys to decrypt. In a digital signature scheme, party A uses its own public and private keys to prepare the message, and party B uses party A""s public key to receive the message. That is, to prepare the message, in a public key encryption scheme, the sending party uses the receiving party""s key information, whereas in a digital signature scheme, the sending party uses its own key information. To receive the message, in a public key encryption scheme, the receiving party uses its own key information, whereas in a digital signature scheme, the receiving party uses the sending party""s key information.
In public key cryptosystems, all participants have a public key and a corresponding private key, as disclosed in U.S. Pat. No. 5,481,613 to Ford et al., entitled xe2x80x9cComputer Network Cryptographic Key distribution Systemxe2x80x9d which is incorporated herein by reference. A shared public key may refer to the portion of the public key common to multiple users, as disclosed in Scott A. Vanstone et al., xe2x80x9cShort RSA Keys and Their Generationxe2x80x9d, 8 Journal of Cryptology, pp. 101-114 (1995) and, U.S. Pat. No. 5,231,668 to Kravitz, entitled xe2x80x9cDigital Signature Algorithmxe2x80x9d, both of which are incorporated herein by reference.
For two participants to be able to communicate using a secret key cryptosystem, the participants must first agree on a secret key to use for their communication. A xe2x80x9csharedxe2x80x9d key in a secret key cryptosystem refers to the secret key agreed upon by the participants, as disclosed in U.S. Pat. No. 5,481,613 to Ford et al., entitled xe2x80x9cComputer Network Cryptographic Key Distribution Systemxe2x80x9d.
Typical digital signature schemes have three steps: system setup, signature generation by a sending party, and signature verification by a receiving party.
System setup is assumed to occur well before signing or encryption of a message. Generally, during system setup of a DL based public key cryptosystem, a prime number is selected and used to obtain a generator for a group, then a random number is selected and used as an exponent for the generator to produce a resulting value in the finite field. Determining the random number when only the generator and resulting value are known is a DL problem.
The outcomes of system setup are a public key and a private key. A public key is assumed to be public knowledge and comprises the prime number, the generator, the resulting value and possibly other parameters. A private key is assumed to be known only to the sending party, and comprises the random number.
During signature generation of a DL based public key cryptosystem, a second random number is chosen and used as an exponent for the generator to produce a second resulting value in the finite field. Determining the second random number when only the generator and second resulting value are known is a DL problem. Then a third value based on the private key, on the message to be signed, and second resulting value is obtained. The outcome of signature generation is a digital signature including the third value and at least one other parameter.
During signature verification of a DL based public key cryptosystem, the public key and third value portion of the signature are exponentially combined to produce a fourth result. If the fourth result is equal to at least one other parameter of the signature, then the signature is considered valid.
The exponentiation portions of system setup, signature generation and signature verification are computationally expensive and time consuming. Techniques are sought which will reduce the computational burden to an authorized user, particularly during signature generation, while maintaining computational difficulty for an unauthorized user.
In accordance with an aspect of this invention, a method of and an apparatus for determining public and private keys for a public key cryptosystem comprises selecting a first prime number, obtaining a cyclotomic polynomial evaluated at the first prime number, obtaining a second prime number which is a factor of the cyclotomic polynomial evaluated at the first prime number, finding a generator of a subgroup of a multiplicative group of a finite field, the order of the subgroup being the second prime number, obtaining a public value based on the generator and a selected integer, forming the public key to include the first and second prime numbers, the generator and the public value, and forming the private key to include the selected integer.
In accordance with a further aspect of this invention, the finite field may be represented with an optimal normal basis.
In accordance with a different aspect of this invention, the second prime number q satisfies (log2 q)+1≈B, where B is a predetermined number of bits.
In accordance with another aspect of this invention, a control integer txe2x80x2 is selected, and the cyclotomic polynomial is the txe2x80x2-th cyclotomic polynomial, and the public key includes the control integer txe2x80x2.
In accordance with still another aspect of this invention, a method of generating a digital signature for a message additionally selects a second integer, obtains a first signature value based on the second integer and the generator, obtains a second signature value based on the first signature value and the message, and forms the digital signature to include the first and second signature values.
A method of verifying a thus-formed digital signature for a message finds an inverse integer which is the inverse of the second signature value, finds a first intermediate value based on the inverse integer and the message, finds a second intermediate value based on the inverse integer and the first signature value, finds a third intermediate value based on the generator, the public value, and the first and second intermediate values, and determines that the signature is valid when the third intermediate value is equal to the first signature value.
A method of determining a shared key for a public key cryptosystem selects a first prime number, obtains a cyclotomic polynomial evaluated at the first prime number, obtains a second prime number which is a factor of the cyclotomic polynomial evaluated at the first prime number, finds a generator of a subgroup of a multiplicative group of a finite field, the order of the subgroup being the second prime number, selects an integer, receives an intermediate value which is based on the generator, and forms the shared key as a function of the intermediate value and the integer.
A method for secure communication of a message selects a first prime number, obtains a cyclotomic polynomial evaluated at the first prime number, obtains a second prime number which is a factor of the cyclotomic polynomial evaluated at the first prime number, finds a generator of a subgroup of a multiplicative group of a finite field, the order of the subgroup being the second prime number, selects an integer, receives an intermediate value which is based on the generator, forms the shared key as a function of the intermediate value and the integer, and encrypts the message using the shared key.
A method for secure communication of a message receives an encrypted message which has been encrypted using a shared key formed as a function of an intermediate value and a selected integer, the intermediate value being based on a generator of a subgroup of a multiplicative group of a finite field, the order of the subgroup being a second prime number which is a factor of a cyclotomic polynomial evaluated at a first prime number, and decrypts the encrypted message using the shared key.
A method for secure communication of a message selects a first prime number, obtains a cyclotomic polynomial evaluated at the first prime number, obtains a second prime number which is a factor of the cyclotomic polynomial evaluated at the first prime number, finding a generator of a subgroup of a multiplicative group of a finite field, the order of the subgroup being the second prime number, obtains a public value based on the generator and a first integer, selects a second integer, finds a first encrypted value based on the generator and the second integer, finds a second encrypted value based on the message, the public value and the second integer, and forms an encrypted message from the first and second encrypted values.
A method for secure communication of a message receives an encrypted message formed of a first encrypted value and a second encrypted value, the first encrypted value being based on a first integer and a generator of a subgroup of a multiplicative group of a finite field, the order of the subgroup being a second prime number which is a factor of a cyclotomic polynomial evaluated at a first prime number, the second encrypted value being based on the message, the first integer and a public value based on the generator and a second integer, finds a first intermediate value based on the first encrypted value and a private key, the private key being based on the generator, and decrypts the encrypted message based on the second encrypted value and the first intermediate value.
It is not intended that the invention be summarized here in its entirety. Rather, further features, aspects and advantages of the invention are set forth in or are apparent from the following description and drawings.